Grokking Algorithm Complexity and Big-O
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Course Overview
Basics of Algorithm Analysis
Introduction to Algorithm Analysis
Measuring Efficiency
Functions and Their Growth Rates
Asymptotic Notations
Overview of Asymptotic Analysis
Big-O Notation (O-notation)
Big-Omega Notation (Ω-notation)
Big-Theta Notation (Θ-notation)
Little-o and Little-omega Notations
Comparing Asymptotic Notations
Time Complexity Analysis
Understanding Time Complexity
Analyzing Control Structures
Analyzing Simple Algorithms
Best, Worst, and Average Cases
Constant Time: O(1)
Linear Time: O(n)
Quadratic Time: O(n²)
Quiz
Space Complexity Analysis
Understanding Space Complexity
Analyzing Space Complexity of Algorithms
Constant Space: O(1)
Linear Space: O(n)
Quadratic Space: O(n²)
Quiz
Analyzing Recursive Algorithms
Introduction to Recursion
Recursion Tree Method
Recurrence Relation Method
Master Theorem Method
Space Complexity Analysis of Recursive Algorithm
Logarithmic Time and Space: O(log n)
Linearithmic Time: O(n log n)
Exponential Time and Space: O(2ⁿ)
Quiz
Array
Linked List
Hash Table and Set
Stack and Queue
Binary Search Tree
Quiz
Sorting Algorithms
Graph Algorithms
Dynamic Programming Algorithms
Coding Interview Problems
Trade-offs in Algorithm Design
Recurrence Relation Method

The Recurrence Relation Method allows us to express the time complexity of a recursive algorithm as a mathematical equation, or recurrence relation, based on the size of the input.

Recurrence relations are equations that express the time complexity of a recursive function in terms of the function itself. This method is useful for algorithms where each recursive call breaks the problem down into smaller subproblems until a base case is reached.

Example: Factorial Function

Let’s analyze the time complexity of a recursive function that calculates the factorial of a number, n!. The factorial of n is defined as the product of all positive integers up to n. We can calculate it using a recursive approach as shown below.

Factorial Code

Java
Saved to Cloud

. . . .
  • Base Case: If n is 0 or 1, the function returns 1. This is the stopping condition, preventing infinite recursion.
  • Recursive Case: For values of n greater than 1, the function calls itself with n - 1, multiplying the result by n each time.

Setting Up the Recurrence Relation

To analyze the time complexity of this recursive function, let’s set up a recurrence relation.

Let:

  • represent the time complexity of calculating the factorial of .

The recurrence relation for factorial(n) is:

Here:

  • : Represents the time complexity of the recursive call, where the function computes factorial(n - 1).
  • : Represents the constant time needed for the multiplication operation .

Solving the Recurrence Relation

Let’s expand this relation step-by-step:

Image

Expanding these terms recursively until we reach the base case, :

Since is a constant, the total complexity of becomes:

The time complexity of the factorial function is , meaning the function requires linear time relative to the input size .

Binary Search Recurrence Relation Analysis

In the previous lesson, we found the time complexity of the binary search by using the recursion tree. Here, we will find the time complexity of the binary search algorithm using the Recurrence Relation Analysis.

In binary search, each recursive call reduces the search range by half. This halving process continues until the range is reduced to a single element, or the base case is reached. Let’s break down the time complexity of this algorithm by setting up a recurrence relation.

Here’s the Python code for binary search, along with comments explaining each step.

Java

. . . .

Setting Up the Recurrence Relation

To analyze the time complexity, let’s define:

  • as the time complexity for binary search on an array of size .

Since each call reduces the search range by half, we can represent this in our recurrence relation as follows:

Where:

  • : Represents the time complexity for a recursive call on half the original input size.
  • : Represents the constant time taken to calculate the middle index and perform the comparison with the target.

Expanding the Recurrence Relation

To solve for , let’s expand the recurrence relation by substituting until we reach the base case:

Image

The recursion stops when the input size is reduced to 1, so we set . Solving for , we get:

Thus, the recursion tree has levels.

Final Complexity Calculation

Since each level requires work and there are levels, the total time complexity of binary search is:

Recursion Tree Method
Master Theorem Method
Mark as Completed

On this page

Example: Factorial Function

Factorial Code

Setting Up the Recurrence Relation

Solving the Recurrence Relation

Binary Search Recurrence Relation Analysis

Binary Search

Setting Up the Recurrence Relation

Expanding the Recurrence Relation